//=============================================================================
/// Buffer Allocator
/**
	K&R "Programming Language C", malloc routine
*/
//=============================================================================

#include "balloc.h"

#ifndef	NULL
#define	NULL	((void*)0)
#endif
#ifndef	FALSE
#define	FALSE	(0)
#define	TRUE	(1)
#endif

typedef union balloc_header Header;

/* init */
void balloc_init(BAlloc* balc, void* buf, unsigned size)
{
	Header* up;

	balc->base.s.ptr = balc->freep = &balc->base;
	balc->base.s.nunits = 0;
	balc->used = balc->marked = NULL;

	up = (Header*)buf;
	up->s.nunits = size / sizeof(Header);
	bfree(balc, up + 1);
}

/* malloc: general memory allocator */
void *balloc(BAlloc* balc, unsigned nbytes)
{
	Header *p, *prevp;
	Header *root;
	unsigned nunits;

	nunits = (nbytes + sizeof(Header) - 1) / sizeof(Header) + 1;
	prevp = root = balc->freep;
	for (p = prevp->s.ptr; ; prevp = p, p = p->s.ptr) {
		if (p->s.nunits >= nunits) {		/* bigger or same */
			Header *q;
			if (p->s.nunits == nunits) {		/* same */
				prevp->s.ptr = p->s.ptr;
				q = p;
			} else {						/* allocate after part */
				p->s.nunits -= nunits;
				q = p + p->s.nunits;
				q->s.nunits = nunits;
			}
			balc->freep = prevp;
			q->s.ptr = balc->used;
			balc->used = q;
			++balc->total_malloc_num;
			return (void*)(q + 1);
		}
		if (p == root)
			return NULL;		/* no memory */
	}
}

#ifdef _DEBUG
#include <string.h>
static void destroy_free_work(void* p, int size) {
	const unsigned char VAL = 0xa5;
	memset(p, VAL, size);
}
#endif

static void remove_from_used_list(BAlloc* balc, Header* bp) {
	Header *prev, *p;
	for (prev = NULL, p = balc->used; p != NULL; prev = p, p = p->s.ptr) {
		if (p == bp) {
			if (prev != NULL) {
				prev->s.ptr = bp->s.ptr;
			} else {
				balc->used = bp->s.ptr;
			}
			break;
		}
	}
}

/* free: put block ap to free list */
void bfree(BAlloc* balc, void* ap)
{
	if (ap != NULL) {
		Header *bp, *p;

		bp = (Header*)ap - 1;		/* pointer to block header */
		for (p = balc->freep; !(p < bp && bp < p->s.ptr); p = p->s.ptr) {
			if (p >= p->s.ptr && (bp > p || bp < p->s.ptr))
				break;		/* begining or ending free block */
		}

#ifdef _DEBUG
		destroy_free_work(ap, (bp->s.nunits-1) * sizeof(Header));
		remove_from_used_list(balc, bp);
#endif
		if (bp + bp->s.nunits == p->s.ptr) {	/* combine to upper nbr */
			bp->s.nunits += p->s.ptr->s.nunits;
			bp->s.ptr = p->s.ptr->s.ptr;
#ifdef _DEBUG
			destroy_free_work(p->s.ptr, sizeof(Header));
#endif
		} else {
			bp->s.ptr = p->s.ptr;
		}
		if (p + p->s.nunits == bp) {			/* combine to lower nbr */
			p->s.nunits += bp->s.nunits;
			p->s.ptr = bp->s.ptr;
#ifdef _DEBUG
			destroy_free_work(bp, sizeof(Header));
#endif
		} else {
			p->s.ptr = bp;
		}
		balc->freep = p;
		++balc->total_free_num;
	}
}



#define	MARK_FLAG	(1<<(sizeof(unsigned) * 8-1))
#define	MARK(ptr)	((ptr)->s.nunits |= MARK_FLAG)
#define	MARKED(ptr)	((ptr)->s.nunits & MARK_FLAG)
#define	UNMARK(ptr)	((ptr)->s.nunits &= ~MARK_FLAG)

int mark(BAlloc* balc, void* work) {
		// search from used list
	Header* h = ((Header*)work) - 1;
	if (!MARKED(h)) {
		Header* pre = NULL;
		Header* p;
		for (p = balc->used; p != NULL; pre = p, p = p->s.ptr) {
			if (p == h) {	// find
				if (MARKED(p)) {
					return FALSE;		// already marked
				}
					// mark
				MARK(p);
					// release from used list
				if (pre != NULL) {
					pre->s.ptr = p->s.ptr;
				} else {
					balc->used = p->s.ptr;
				}
					// move to marked
				p->s.ptr = balc->marked;
				balc->marked = p;
				return TRUE;
			}
		}
	}
	return FALSE;
}

void sweep(BAlloc* balc) {
	Header* p;
	// release unmarked blocks
	//	used is unmarked
	for (p = balc->used; p != NULL; ) {
		Header* q = p->s.ptr;
		void* work = p + 1;		// lent pointer
		bfree(balc, work);
		p = q;
	}
	// reset mark flag and back to used list
	balc->used = balc->marked;
	balc->marked = NULL;
	for (p = balc->used; p != NULL; p = p->s.ptr) {
		UNMARK(p);
	}
}


int balloc_get_info(BAlloc* balc, int* p_total_free_size, int* p_max_block_size) {
	unsigned int max_units = 0;
	unsigned int nunits = 0;
	Header* p;
	for (p = &balc->base; p = p->s.ptr, p != &balc->base; ) {
		unsigned int n = p->s.nunits - 1;
		nunits += n;
		if (max_units < n)	max_units = n;
	}
	*p_total_free_size = nunits * sizeof(Header);
	*p_max_block_size = max_units * sizeof(Header);

	return balc->total_malloc_num - balc->total_free_num;
}

